#include <stdio.h>
#include <stdlib.h>

//二叉树节点
typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
//二叉搜索树
typedef struct
{
    struct TreeNode *root;
} BinarySearchTree;
//初始化二叉树
TreeNode *new_tree_node(int val)
{
    TreeNode *node = malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}
//初始化二叉搜索树
BinarySearchTree *new_binary_search_tree()
{
    BinarySearchTree *tree = malloc(sizeof(BinarySearchTree));
    tree->root = NULL;
    return tree;
}

// 代码实现二叉搜索树的查找
TreeNode *search(BinarySearchTree *tree, int data)
{
    // 先拿到二叉搜索树的根节点, 根据二叉搜索树特性,不断的向下查询对应方向的子节点
    TreeNode *cur = tree->root;

    while (cur != NULL && cur->val != data)
    {
        // 当前树节点值大于查询目标值, 向左子树内部查询
        if (cur->val > data)
        {
            cur = cur->left;
        }
        else if (cur->val < data) // 当前树节点值小于查询目标值, 向右子树内部查询
        {
            cur = cur->right;
        }
    }

    return cur;
}
//代码实现二叉搜索树的插入
void insert(BinarySearchTree *bst, int num)
{
    if (bst->root == NULL)
    {
        bst->root = new_tree_node(num);
        return;
    }

    TreeNode *cur = bst->root;
    TreeNode *pre = NULL;

    while (cur != NULL)
    {
        pre = cur; // 使用pre记录上一个节点
        if (cur->val > num)
        {
            cur = cur->left;
        }
        else if (cur->val < num)
        {
            cur = cur->right;
        }
        else
        { // cur->val == num 该数字已经在二叉搜索树上了,无需再插入
            return;
        }
    }

    TreeNode *node = new_tree_node(num);

    if (pre->val > num) //当前节点值大于插入值，将插入值插到当前节点的左子节点
    {
        pre->left = node;
    }
    else                //当前节点值小于插入值，将插入值插到当前节点的右子节点
    {
        pre->right = node;
    }
}
//中序遍历二叉树
void inOrder(TreeNode *root)
{
    if (!root) // root == NULL
    {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}
//代码实现二叉搜索树的删除功能
void removeItem(BinarySearchTree *bst, int num)
{
    // 若树为空，直接提前返回
    if (bst->root == NULL)
    {
        return;
    }

    TreeNode *cur = bst->root;
    TreeNode *pre = NULL;

    while (cur != NULL)
    {
        // 判断 cur 等于要删除的目标值方法必须写在 pre = cur 前面
        // 找到当前节点, pre不能更新要拿上一级节点
        if (cur->val == num)
        {
            break;
        }

        pre = cur; // 使用pre记录上一个节点

        if (cur->val > num)
        {
            cur = cur->left;
        }
        else if (cur->val < num)
        {
            cur = cur->right;
        }
    }

    // 考虑删的目标值,不在树中不删除
    if (cur == NULL)
    {
        return;
    }

    // 判断 cur 有几个子节点, 0 1删起来简单, 2比较复杂
    if (cur->left == NULL || cur->right == NULL)
    { // 至少有一个节点为空
        // 先拿到 cur 的唯一后代节点(若 cur 度为 0 后代都是NULL随便挑一个就好)
        TreeNode *child = cur->left != NULL ? cur->left : cur->right;
        // 通过pre的值判断cur到底是pre左子结点还是右子节点
        if (pre->val > cur->val)
        {
            pre->left = child;
        }
        else
        {
            pre->right = child;
        }
        // 释放内存
        free(cur);
    }
    else
    {
        // 当二叉搜索树要删除子节点为2(度为2)的节点时
        // 操作方式找到以当前节点为根节点的 中序遍历 下一个节点 Next
        // 删除 Next ,让当前节点的值更新为Next的值
        // 注意: Next节点他的度一定不为 2
        // 找 Next
        TreeNode *next = cur->right;
        // 一直往左走找到next->left 为 NULL 此时 next就是我们要找的中序遍历 cur 的后继结点
        while (next->left != NULL)
        {
            next = next->left;
        }
        // 创建变量保留next的值,一会用于替换cur的值
        int tmp = next->val;
        // 删除 next, next的度一定小于二, 这里函数调用自身删除next的值,所以他会走上面的if语句
        // if(cur->left == NULL || cur->right == NULL) 里面的功能我们已经实现了
        removeItem(bst, tmp);
        // 替换cur的值为tmp
        cur->val = tmp;
    }
}

int main(int argc, char const *argv[])
{
    BinarySearchTree *tree = new_binary_search_tree();

    insert(tree, 8);
    insert(tree, 4);
    insert(tree, 2);
    insert(tree, 6);
    insert(tree, 1);
    insert(tree, 3);
    insert(tree, 5);
    insert(tree, 7);

    insert(tree, 12);
    insert(tree, 10);
    insert(tree, 14);
    insert(tree, 9);
    insert(tree, 11);
    insert(tree, 13);
    insert(tree, 15);
    insert(tree, 16);

    removeItem(tree,14);
    removeItem(tree,12);
    removeItem(tree,4);
    inOrder(tree->root);


    return 0;
}
